package com.hhc.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Leetcode239 难度：困难
 * 给定一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 只可以看到在滑动窗口内的k个数字，滑动窗口每次只向右移动一位。
 * 返回滑动窗口中的最大值
 * 示例：
 * 输入：nums=[1,3,-1,-3,5,3,6,7],k=3
 * 输出：[3,3,5,5,6,7]
 *
 * 求解思路：窗口可以看作是一个单调队列，添加元素之前如果前面有比他小的都要移除，
 * 保证队列单调性，即从左往右是递减的。所以队列中的最大值就是最左边的元素。
 */
public class T239 {
    public static int[] maxSlidingWindow(int[] nums,int k){
        int index=0,len = nums.length;
        int[] ans = new int[len -k +1];
        // 双端队列，存储元素下标
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0;i < len; i++){
            // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要出窗口了，就把队头元素给移除
            if(!deque.isEmpty() && deque.peekFirst() <= i-k){
                deque.pollFirst();
            }
            // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口中队列头部元素永远是队列中最大的
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.pollLast();
            deque.addLast(i); // 当前元素的下标加入到队列的尾部
            // 当窗口的长度大于等于k个的时候才开始计算 (这里的i 是从0开始)
            if(i >= k-1)
                // 队头元素时队列中最大的，把队列头部的元素加入到数组中
                ans[index++] = nums[deque.peekFirst()];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] ans = maxSlidingWindow(nums,k);
        for(int i = 0;i<ans.length; i++){
            System.out.println(ans[i]);
        }
    }
}
